互素(Coprime)
$\Leftrightarrow(a,b)=1$
贝朱定理$\Rightarrow \exists x,y \in Z \; s.t.ax+by=1$
$ad|a,d|b\Rightarrow d|1$
定理一
$a,b,c\in Z$
$\begin{cases}a|bc\\\(a,b)=1\end{cases}\Rightarrow a|c$
证明
$\because (a,b)=1 \therefore \exists u,v\in Z,s.t.$
$ai+bv=1$
$\Downarrow$
$acu+bcv=c$
$\because a|acu,a|bcv \therefore a|c$
定理二
$\begin{cases}a|c,b|c\(a,b)=1\end{cases}\Rightarrow ab|c$
证明
$a|c\Rightarrow c=ak,k\in Z$
$\begin{cases}b|ak\(a,b)=1\end{cases}\Rightarrow b|k \Leftrightarrow k=bl ,l\in Z$
$c=abl$
$\therefore ab|c$
定理三
$\begin{cases}a|b_1c\\a|b_2c\(b_1,b_2)=1\end{cases}\Rightarrow a|c$
证明
$\exists u,v \in Z \;s.t.$
$b_1u+b_2v=1$
$\Downarrow$
$b_1cu+b_2cv=c$
$\because a|b_1cu,a|b_2cv$
$\therefore a|c$
定理四
$(a,b)=1,(a,c)=1$
则$(a,bc)=1$
证明
$au_1+bv_1=1,au_2+cv_2=1$
两式相乘
$a^2u_1u_2+acu_1v_2+abu_2v_1+bcv_1v_2=1$
$\Downarrow$
$a(\;\;\;\;\;)+bcv_1v_2=1\Rightarrow (a,b)=1$
- $(a_i,b_j)=1,i=1,2,\cdots,j=1,2,\cdots\Rightarrow (a_1a_2\cdots a_i,b_1b_2\cdots b_j)=1$
- $(a,b)=1\Rightarrow (a^n,b^m)=1,m,n\in Z$
素数(prime)
定义
p是素数$\Leftrightarrow $只有$\pm1,\pm p$是它的因子
- $a\in Z\;\; p:素数 ，则p|a或者(p,a)=1$
- $p:素数，a,b\in Z,则，p|ab\Rightarrow p|a或p|b$
算数基本定理
任一个大于1的整数，都唯一分解为一些素数的乘积。
同余
$a,b\in \Z.m>1$
$a,b关于模m同余 \Leftrightarrow m|a-b$
$记为：a \equiv b(mod \;m)$
- m:(modulo)
性质
1.
$a \equiv b,c \equiv d(mod\; m)$
$a\pm c = b\pm d(mod \;m) $
$ac\equiv bd(mod \ m)$
$ac-bd$
$=ac-bc+bc-bd$
$=(a-b)c+b(c-d)$
2.
$a\equiv b\ (mod \ m)$
$a^n\equiv b^n\ (mod \ m)$
3.
$\begin{cases}(k,m)=1\\ka\equiv b\ (mod \ m)\end{cases}\Rightarrow a\equiv b\ (mod\ m)$
==4.==
$(a,m)=1,则ax\equiv b\ (mod \ m)一定有唯一的解$
$ax=b\ mod \ m\Leftrightarrow m|(ax-b)\Leftrightarrow ax-b=my\Leftrightarrow ax-my=1$
$\because (a,m)=1\therefore \exists u,v\in \Z$
$s.t. \ au+mv=1$
$\Downarrow$
$abu+mbv=b$
$a(bu)\equiv b\ (mod \ m)$
$ax_1\equiv \ b,ax_2\equiv b \ (mod \ m)$
$a(x_1-x_2)\equiv 0\ (mod\ m)$
$\therefore x_1-x_2=0\ (mod\ m)$
中国剩余定理(Chinese Remainden Theorem )
$m_1,m_2,\cdots,m_s两两互素((m_i,m_j)=1,i\neq j)$
$x\equiv a_1\ (mod\ m)$
$x\equiv a_2\ (mod\ m)$
$\vdots$
$x有唯一解$
分析
$令M=\prod\limits_{i=1}^sm_i$
$M_i=\frac{M}{m_i}\Rightarrow (m_i,M_i)=1$
$\exists b_i\in \Z$
$s.t.$
$M_ib_i\equiv 1(mod\ m_i)$
$令x=a_1M_1b_1+a_2M_2b_2+\cdots+a_sM_sb_s$
$则x是上述同余方程组的解$
模m剩余类
定义
给定$m>1,\{[0],[1],\cdots,[m-1]\}称为模m剩余类$
$\Downarrow$
$群(存在0，存在加法，存在交换律，存在相反数)$
$[a]+[b]\triangleq[a+b]$
$\begin{cases}a\equiv a’\\b\equiv b’\end{cases}$
$a+b\equiv a’+b’$
$[a+b]=[a’+b’]$
$[a][b]\triangleq [ab]$
$[a]\neq 0,[a][b]=[1]\Leftrightarrow ax \equiv 1 \pmod{m}$
$[a]\neq 0有逆元$
$m>1,每个类都去一个，叫完全代表元$
简化剩余系
定义
m的剩余系中与m互素的部分
性质
$令a_1,a_2,\cdots,a_s为m的一个简化（缩）剩余系，即(m,a_i)=1$
$令(k,m)=1$
$则ka_1,ka_2,\cdots,ka_s也是一个简化剩余系$
$\begin{cases}(a_i,m)=1\(k,m)=1\end{cases}\Rightarrow(ka_i,m)=1$
* $\begin{cases}ka_i\equiv a_j \bmod m\(k,m)=1\end{cases}\Rightarrow a_i \equiv a_j \bmod m$
* $a_1a_2\cdots a_s\equiv k^sa_1a_2\cdots a_s \bmod m$
* $k^s\equiv 1 \bmod m$
欧拉函数
定义
$s=\varphi(m):与m互素的1,2,3,\cdots,m-1之间的整数对$
性质
$a^{\varphi(m)}\equiv 1 \bmod m,(a,m)=1$
费马小定理
若p为素数，则$a^{p-1}\equiv \bmod p,(a,p)=1$
$a^p\equiv a \bmod p$